package org.pupil.list.addTwoNumbers;

import org.pupil.list.ListNode;
import org.pupil.list.IList;

/**
 * @Description: 两个链表相加
 * @Author: pupil
 * @Date: 2024/07/29 下午 12:15
 */
public class AddTwoNumbers {

    /**
     * 题目介绍：
     * 给定两个非空链表 h1和 h2 来代表两个非负整数。数字最低位于链表开始位置。
     * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * 可以假设除了数字 0 之外，这两个数字都不会以零开头。
     *
     *    4  8  9
     * +  2  6  7  9
     *
     * 1. 4+2=6   值：6  进位：0  链表：6->null
     * 2. 8+6=14  值：4  进位：1  链表：6->4->null
     * 3. 9+7=16  值：7  进位：1  链表：6->4->7->null
     * 4. 0+9=9   值：0  进位：1  链表：6->4->7->0->null
     * 5. 链表遍历完，但是有进位：1，需要处理，链表：6->4->7->0->1->null
     *
     * @param h1
     * @param h2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode h1, ListNode h2) {
        ListNode ans = null; // 标记头节点
        ListNode cur = null; // 标记当前节点

        int carry = 0; // 进位

        for (int sum, val; // 声明变量
             h1 != null || h2 != null; // 终止变量
             h1 = h1 == null ? null : h1.next, // 每一步h1的跳转
                     h2 = h2 == null ? null : h2.next // 每一步h2的跳转
        ) {

            // 和数
            sum = (h1 == null ? 0 : h1.val)
                    + (h2 == null ? 0 : h2.val)
                    + carry;

            // 节点值
            val = sum % 10;
            // 进位
            carry = sum / 10;

            if (ans == null) {
                ans = new ListNode(val);
                cur = ans;
            } else {
                cur.next = new ListNode(val);
                cur = cur.next;
            }
        }

        if (carry == 1) {
            cur.next = new ListNode(1);
        }
        return ans;
    }


    public static void main(String[] args) {
        ListNode h1 = IList.get(new int[]{4, 8, 9});
        ListNode h2 = IList.get(new int[]{2, 6, 7, 9});

        ListNode listNode = addTwoNumbers(h1, h2);
        IList.ergodic(listNode);
    }
}
